Rule-based artificial intelligence systems, generally known as expert systems, typically include a set of rules, forming a "knowledge base", one or more facts in a working memory, and an inference engine that manipulates the rules in response to the facts in the working memory. By a process known as "inference", the inference engine attempts to match conditions in each of the rules to the facts in the working memory. If the conditions of a particular rule match the facts, the rule is said to "fire", and the inference engine then performs actions or operations specified in the rule. These operations may include, for example, addition, deletion and/or modification of facts in the working memory, transmission of results to a user, and so forth. The condition matching/firing sequence is sometimes referred to as a "recognize/act" cycle, with "recognize" referring to the portion of the operation in which the inference engine compares conditions of the rules to the facts in working memory to determine which, if any, rules fire, and "act" referring to the portion of the operation in which the inference engine actually performs the actions and operations specified in the rule. If, during firing of a rule, the inference engine adds, deletes or modifies a fact, the inference engine may repeat these operations in response to the new or modified facts in the working memory, which may, in turn, cause other rules to fire. Rule processing begins when an addition, modification or deletion is made to the facts in the working memory, and proceeds iteratively until no further additions, modifications or deletions are made to the facts in the working memory.
More particularly, each rule includes one or more conditions, which are collectively referred to as the "left-hand side", and a "right-hand side" which contains an action list, which identifies one or more operations performed if the rule fires. The facts in the working memory are typically organized as one or more relations, with each relation comprising one or more entries, or items of data. Each entry in a relation, in turn, is identified as having one or more slots. Each relation is identified by a class name, and each slot is identified by a slot name. A condition identifies a relation by class name, one or more slots, by name, and, optionally, a set of limits or requirements on the values for each named slot. In the comparison operation, the inference engine determines whether the relation in the working memory that corresponds to the class name in the condition contains an entry whose slot values correspond to the slot values set forth in the condition. If so, the condition is satisfied. However, if the working memory does not have an entry whose slots contain the values specified in the condition, the condition is not satisfied. To determine whether a rule is in condition to fire, the inference engine performs the existence test in connection with each condition in the rule.
The existence test can be somewhat more complicated, particularly in connection with a rule in which one or more of a condition's slot values are expressed as variable values. If a condition identifies a class and one or more slot values, at least one of which is specified by a variable and the values identified for each of the other slot names match the values in their corresponding slots in the working memory entry, the condition is satisfied by each entry in the relation identified by the class name in which the variable is satisfied. In the match operation for a condition with a variable, the inference engine establishes one or more binding lists for the variables that identify the set of values in the slots in the various entries in the relation which can satisfy the condition. The values of the variables in each binding list are propagated through subsequent conditions comprising the rule's left hand side to determine whether each successive condition is satisfied, with each set of values comprising the binding lists that satisfy the rule resulting in a different instantiation of the rule. The inference engine may then perform a conflict resolution operation among the rules and instantiations to select a rule, and specifically an instantiation if the rule has multiple instantiations, for firing.
One way in which the inference engine may determine if the rules' conditions are satisfied is to test each of the conditions of each of the rules against the facts in the working memory and keep track of the rules whose conditions are satisfied. However, in many circumstances the same condition is included in a number of rules. Further, in most circumstances, it is not necessary to evaluate every working memory relation against every rule during every recognize/act cycle. Instead, partial lists of relation/rule associations can be maintained and incremental updates performed to these lists as relations are added, deleted or modified. To avoid the necessity of testing or retesting such conditions for each rule, reticular, or "RETE" networks have been developed. In a reticular network, the conditions of all the rules are organized as a series of test nodes, with one test node being associated with each condition. Each of the rules, in turn, is represented by a terminal node. The test nodes are connected to the terminal nodes through a network of join nodes, each of which represents a logical operation in connection with each successive condition in the rule. During the "recognize" portion of the recognize/act cycle, tokens are passed between the nodes representing successful comparisons, with the tokens that eventually reach the terminal node representing the various instantiations of the rule. These tokens which represent successful comparisons are termed "beta tokens."
In beta-token partitioning systems, these beta tokens are divided among multiple processors of a computer system in order to approximately equally divide the computational load among the processors.